A wireless ad-hoc network, also sometimes referred to as a mobile ad-hoc network (MANET), is known to comprise a set of nodes connected by wireless links. Typical examples of ad-hoc networks are wireless sensor networks, where the nodes are sensors that gather environmental data and send the information to computational nodes for further processing, or to base stations for relay to a wired network. Such networks may be deployed, for example, in hazardous locations such as in disaster areas (e.g., earthquakes, fires, etc.) to aid rescue efforts, in areas for mineral or oil prospecting, and in battlefields for defense applications. Ad-hoc networks may also be realized in the form of a short-lived network among people attending a business meeting.
The topology of an ad-hoc network is typically dynamic since nodes are free to move randomly and organize themselves arbitrarily. Therefore, the topology may be determined by the current geographic location of the nodes and other environmental conditions, and the characteristics of the radio transceivers that the nodes possess. The topology may therefore be represented as an arbitrary graph with “nodes” of the graph representing nodes in the network and “edges” of the graph representing links between nodes.
The nodes in an ad-hoc network typically attempt to communicate amongst each other by relaying packets. However, due to the limited transmission range that is characteristic of nodes in an ad-hoc network, multiple network “hops” are typically needed for one node to exchange data with another node across the network. The problem is to design efficient routing protocols to meet a variety of performance objectives given such a communications environment.
Routing efficiently in wireless ad-hoc networks poses many challenges. Some commonly studied problems include: (i) how to handle the frequent changes in the network topology due to mobility of the users, and/or failure of wireless links caused by obstruction or fading of signals; (ii) how to maintain the long multi-hop paths between two communicating nodes; and (iii) how to reduce the interference among the various users wishing to transmit, which is caused due the absence of any centralized control.
Another direction in the quest for efficient routing protocols was introduced by the work of Gupta and Kumar which focused on the capacity of wireless ad-hoc networks, see Piyush Gupta and P. R. Kumar, “The Capacity of Wireless Networks, IEEE Transactions on Information Theory, 46(2):388-404, 2000, the disclosure of which is incorporated by reference herein. Gupta and Kumar first show an upper bound on the maximum possible transmission capacity achievable by any static ad-hoc wireless network and then illustrate a routing protocol for a random network which has capacity close to the optimum. Such a result, though it ignores many issues which arise in practical settings, offers important theoretical insights into the problem.
Gupta and Kumar show that the average available throughput per node decreases as the square root of the number of nodes n in a static ad-hoc network. Equivalently, the total network capacity increases as, at most, √{square root over (n)}. Their result holds quite generally In particular, it holds irrespective of the network topology, power control policy or any transmission scheduling strategy.
Given this limitation on the achievable throughput, a natural question which arises is whether the average throughput available per node can be increased. There are two approaches discussed in the literature which attempt to address this question.
The first approach is to add relay-only nodes in the network. This increases the total network capacity, thus increasing the share available to each sender, see Gupta and Kumar. However, a major drawback of this scheme is that the number of relay nodes required is substantial. For example, in a network with 100 senders, at least 4476 relay nodes would be needed to increase the capacity five-fold.
The second approach is to add mobility. In a network where nodes move randomly in a circular disk such that their steady state distribution is uniform, Grossglauser and Tse show that it is possible for each sender-receiver pair to obtain a constant fraction of the total available bandwidth, see Mathias Grossglauser and David Tse, “Mobility Increases the Capacity of Ad-hoc Wireless Networks,” In Proceedings of IEEE Infocom '01, Apr. 2001, the disclosure of which is incorporated by reference herein. This constant remains independent of the number of sender-receiver pairs.
However, as noted in Grossglauser and Tse, such a scheme does not provide any guarantee on the time that it takes for the packet to reach its destination, or on the size of the buffers needed at the intermediate relay nodes. In general, the delay to deliver the packet could be arbitrarily large.
Accordingly, a need still exists for efficient routing techniques that meet performance objectives associated with an ad-hoc network environment and the like.